힙 (자료 구조)

3. 이진 힙 (Binary Heap)

이진 힙은 이진 트리를 기반으로 하는 자료 구조로, 특정한 속성을 만족하도록 구성된다.

이진 힙은 배열을 이용하여 구현할 수 있다. 배열을 사용하면 힙의 노드와 그 관계를 쉽게 나타낼 수 있다.

• 배열의 각 요소는 힙의 노드를 나타낸다.
• 부모/자식 관계는 배열 요소의 인덱스를 통해 암시적으로 정의된다.

• '''삽입''': 힙의 끝, 즉 첫 번째 사용 가능한 빈 공간에 새 요소를 추가한다. 힙 속성을 위반하는 경우, 힙 속성이 다시 설정될 때까지 새 요소를 sift up (''swim'' 연산)한다.
• '''추출''': 루트를 제거하고 힙의 마지막 요소를 루트에 삽입한다. 힙 속성을 위반하는 경우, 힙 속성을 다시 설정하기 위해 새 루트를 sift down (''sink'' 연산)한다.
• '''교체''': 루트를 제거하고 "새" 요소를 루트에 넣고 sift down한다. 삽입 후 추출과 비교하면 sift up 단계를 피할 수 있다.

3. 1. 구조

• 뿌리 노드를 제외한 각 내부 노드는 `key(T.parent(v)) < key(v)` 또는 `key(T.parent(v)) > key(v)`이다. (키 값은 오름차순 또는 내림차순)
• 마지막 왼쪽 결합 노드들의 레벨을 제외한 다른 모든 레벨들은 완전 이진 트리를 형성한다.^[9]

makeTreeHeap(H,n) //H full binary Tree, data size n

for(i <= H/2;i>=1;i <- i-1) do //부모노드 레벨의 역행(4-,3-,2-,1번째)

{

p <- i;// 중간지점에서 시작

for(j<- 2*p;j<=n;j <- 2*j) do //해당 부모노드의 자식노드들에 대한 비교 교환

{

if(j
if(H[j] < H[j+1]) then j <- j+1

if(H[p] >= H[j]) exit;

temp <- H[p];

H[p] <- H[j];

H[j] <- temp;

p <- j;

}

}

makeTreeHeap(H,n) //H full binary Tree, data size n

for(i <= H/2;i>=1;i <- i-1) do //부모노드 레벨의 역행(4-,3-,2-,1번째)

{

p <- i;// 중간지점에서 시작

for(j<- 2*p;j<=n;j <- 2*j) do //해당 부모노드의 자식노드들에 대한 비교 교환

{

if(j
if(H[j] < H[j+1]) then j <- j+1

if(H[p] >= H[j]) exit;

temp <- H[p];

H[p] <- H[j];

H[j] <- temp;

p <- j;

}

}

4. 응용

• 힙 정렬: 제자리 정렬 방식이며 최악의 경우에도 이차 시간이 걸리지 않는 최고의 정렬 방법 중 하나이다.
• 선택 알고리즘: 힙은 최소 또는 최대 요소에 상수 시간에 접근할 수 있으며, 중앙값 또는 k번째 요소와 같은 다른 선택은 힙에 있는 데이터에서 서브 선형 시간 내에 수행할 수 있다.^[8]
• 그래프 알고리즘: 힙을 내부 순회 데이터 구조로 사용하면 실행 시간이 다항식 차수만큼 줄어든다. 이러한 문제의 예로는 프림의 최소 신장 트리 알고리즘과 다익스트라의 최단 경로 알고리즘이 있다.
• 우선순위 큐: 우선순위 큐는 "목록" 또는 "맵"과 같은 추상적인 개념이며, 목록을 연결 목록 또는 배열로 구현할 수 있는 것처럼 우선순위 큐는 힙 또는 다양한 다른 방법으로 구현할 수 있다.
• K-웨이 병합: 힙 자료 구조는 이미 정렬된 여러 입력 스트림을 단일 정렬된 출력 스트림으로 병합하는 데 유용하다. 병합의 필요성의 예로는 외부 정렬 및 로그 구조 병합 트리와 같은 분산 데이터에서 스트리밍 결과가 있다. 내부 루프는 최소 요소를 얻고, 해당 입력 스트림에 대한 다음 요소로 대체한 다음, 힙 다운 연산을 수행한다. (또는 대체 기능). (우선순위 큐의 최대 추출 및 삽입 함수를 사용하는 것은 훨씬 덜 효율적이다.)

5. 프로그래밍 언어별 구현

• C언어로 구현된 최대 힙의 예시는 다음과 같다.

• C++ 표준 라이브러리는 힙에 대한 , 및 알고리즘을 제공한다.
• 부스트 C++ 라이브러리에는 ''d''-ary, 이항, 피보나치, 페어링 및 스큐 힙과 같은 추가 유형의 힙을 지원하는 힙 라이브러리가 포함되어 있다.
• C 및 C++를 위한 [https://github.com/valyala/gheap 일반 힙 구현]이 있으며, D-ary 힙 및 B-힙을 지원한다.
• D 프로그래밍 언어의 표준 라이브러리에는 [https://dlang.org/phobos/std_container_binaryheap.html ]가 포함되어 있다.
• Haskell의 경우 [https://hackage.haskell.org/package/heaps ] 모듈이 있다.
• Java 플랫폼은 Java 컬렉션 프레임워크의 클래스를 사용하여 이진 힙 구현을 제공한다.
• Python에는 이진 힙을 사용하여 우선 순위 큐를 구현하는 [https://docs.python.org/library/heapq.html ] 모듈이 있다.
• PHP는 표준 PHP 라이브러리의 버전 5.3부터 최대 힙 ()과 최소 힙 ()을 모두 가지고 있다.
• Perl은 CPAN에서 사용할 수 있는 [https://metacpan.org/module/Heap ] 배포판에 이진, 이항 및 피보나치 힙의 구현을 가지고 있다.
• Go 언어에는 [http://golang.org/pkg/container/heap/ ] 패키지가 포함되어 있다.
• 애플의 Core Foundation 라이브러리에는 [https://developer.apple.com/documentation/corefoundation/cfbinaryheap ] 구조체가 포함되어 있다.
• Pharo는 Collections-Sequenceable 패키지에 힙 구현을 가지고 있다.
• Rust 프로그래밍 언어는 표준 라이브러리의 모듈에 이진 최대 힙 구현인 [https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html ]를 가지고 있다.
• .NET은 [https://docs.microsoft.com/dotnet/api/system.collections.generic.priorityqueue-2 PriorityQueue] 클래스를 가지고 있다.

참조

_[1] 간행물 "heap" in [[Dictionary of Algorithms and Data Structures]] https://xlinux.nist.[...] National Institute of Standards and Technology 2004-12-14
_[2] 서적 INTRODUCTION TO ALGORITHMS The MIT Press Cambridge, Massachusetts London, England
_[3] 논문 Algorithm 232 - Heapsort
_[4] 웹사이트 heapq.heappush https://docs.python.[...]
_[5] 웹사이트 heapq.heappop https://docs.python.[...]
_[6] 웹사이트 heapq.heapreplace https://docs.python.[...]
_[7] 논문 Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program IOS Press
_[8] 논문 Information and Computation http://ftp.cs.purdue[...] Academic Press 2010-10-31
_[9] 문서 레벨 포화 상태(saturated status on level)